package com.cat.dataStructure;

import java.util.*;

/**
*   @description https://leetcode.cn/problems/sum-of-distances/description/
*   @author 曲大人的喵
*   @create 2025/8/19 16:05
*   @since JDK17
*/

public class Solution37 {
    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] ans = new long[n];
        long[] prefix = new long[n + 1];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        // 分组
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        for (ArrayList<Integer> list : map.values()) {
            int m = list.size();
            for (int i = 0; i < m; i++) {
                prefix[i + 1] = prefix[i] + list.get(i);
            }
            for (int i = 0; i < m; i++) {
                int idx = list.get(i);
                long left = (long) i * idx - prefix[i];
                long right = prefix[m] - prefix[i] - (long) (m - i) * idx;
                ans[idx] = left + right;
            }
        }

        return ans;
    }
}
